import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-04
 * Time: 上午 08:07
 */
public class Test {
    private static void quick(int[] arr, int start, int end){
        if (start >= end) return;
        //三数取中优化
        int mid = threeNum(arr, start, end);
        int tmp = arr[start];
        arr[start] = arr[mid];
        arr[mid] = tmp;
        int pivot = getPivot1(arr,start, end);
        int ret = arr.length / 2;
        if (pivot == ret) {
            System.out.println(arr[pivot]);
            return;
        }
        quick(arr, start,pivot - 1);
        quick(arr, pivot + 1, end);
    }
    //挖坑法找基准
    private static int getPivot1(int[] arr, int left, int right){
        int key = arr[left];
        while (left < right){
            while (left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while (left < right  && arr[left] <= key) left++;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    //三数取中法优化
    private static int threeNum(int[] arr, int left, int right){
        int mid = (left + right) / 2;
        if (arr[left] < arr[right]){
            if (arr[mid] < arr[left]) return left;
            else if (arr[mid] > arr[right]) return right;
            else return mid;
        }else{
            if (arr[mid] > arr[left]) return left;
            else if (arr[mid] < arr[right]) return right;
            else return mid;
        }
    }
    public static void main(String[] args) {

        int[] arr = {2,4,1,3,5};
        quick(arr,0, arr.length - 1);
    }
}
